package com.jack.leetcode.eachProblem07;

public class 分割数组的最大值 {

    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        long sum = nums[0], max = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            max = max > nums[i] ? max : nums[i];
        }
        while (max < sum) {
            int cnt = 1;
            long tmp = 0;
            long mid = (max + sum) / 2;
            for (int i : nums) {
                tmp += i;
                if (tmp > mid) {
                    tmp = i;
                    ++cnt;
                }
            }
            if (cnt > m) {
                max = mid + 1;
            } else {
                sum = mid;
            }
        }
        return (int) max;
    }
}
